package main.java.com.pzhu.algorithm;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * 169. 多数元素
 * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 * <p/>
 * 示例 1：
 * <p/>
 * 输入：nums = [3,2,3]
 * 输出：3
 * 示例 2：
 * <p/>
 * 输入：nums = [2,2,1,1,1,2,2]
 * 输出：2
 * <p/>
 * 提示：
 * n == nums.length
 * 1 <= n <= 5 * 104
 * -109 <= nums[i] <= 109
 * <p/>
 * 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
 *
 * @author rediaz
 * @date 2024-07-21
 */

public class _009mostElements {


    /**
     * 摩尔投票算法（Boyer-Moore Voting Algorithm）
     * 这个方法使用了一种称为摩尔投票算法的技术来找到多数元素。这种算法的时间复杂度是O(n)，空间复杂度是O(1)，符合题目进阶要求。
     * 初始化：设置两个变量，count用来跟踪候选元素的当前票数，初始为0；candidate用来存储当前的候选多数元素，初始为null。
     * 遍历数组：对于数组中的每一个元素num执行以下操作：
     * 如果count为0，那么将num设为新的候选元素candidate。
     * 如果num等于candidate，则增加count的值；否则减少count的值。
     * 返回结果：遍历结束后，candidate变量将持有多数元素。
     * 这种方法的原理在于，由于多数元素出现次数超过数组长度的一半，所以当遍历过程中所有非多数元素与多数元素相互抵消后，多数元素的计数器仍然会是正数，因此最后剩下的candidate就是多数元素。
     * 注意事项
     * 虽然摩尔投票算法可以找到一个可能的多数元素，但在严格意义上，为了验证这个元素确实是多数元素，我们还需要再次遍历数组，计算该元素出现的次数是否真的大于n/2。
     * 不过，根据题目的前提条件，“给定的数组总是存在多数元素”，我们可以省略这一步骤，直接返回candidate作为答案。
     *
     * @param nums
     * @return
     */
    public Integer majorityElement(int[] nums) {
//        int count = 0;
//        Integer candidate = null;
//
//        for (int num : nums) {
//            if (count == 0) {
//                candidate = num;
//            }
//            count += (num == candidate) ? 1 : -1;
//        }
//
//        return candidate;
        int count = nums.length;
        Arrays.sort(nums);
        return nums[count / 2];



    }

    public static void main(String[] args) {
        System.out.println(new _009mostElements().majorityElement(new int[]{2, 2, 1, 1, 1, 2, 2}));
        System.out.println(new _009mostElements().majorityElement(new int[]{3, 2, 3}));
    }

}
